package cn.atguigu.likedlist;

import java.util.List;
import java.util.Stack;

public class SingleLikedList {

    public static void main(String[] args) {
        SingleLikedList singleLikedList = new SingleLikedList();
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode3 = new HeroNode(3,"智多星","吴用");
        HeroNode heroNode4 = new HeroNode(4,"入云龙","公孙胜");
        singleLikedList.addOrderByNo(heroNode1);
        singleLikedList.addOrderByNo(heroNode4);
        singleLikedList.addOrderByNo(heroNode2);
        singleLikedList.addOrderByNo(heroNode3);
        System.out.println(singleLikedList.length());
        singleLikedList.showList();

        System.out.println("链接反转");

        reverse(singleLikedList.getHead());
        singleLikedList.showList();
        System.out.println("反转打印");
        reversePrint(singleLikedList.getHead());


    }

    //头结点不能动
    private HeroNode head=new HeroNode(0,"","");

    //添加。要求按照顺序添加
    public void addOrderByNo(HeroNode newNode){
        HeroNode temp = head;
        boolean flag = false;

        //找到节点
        while (true){
            if(temp.next == null){
               break;
            }
            //找到要插入的位置，这个位置要在插入节点之前
            if(temp.next.no > newNode.no){
                break;
            }else if (temp.next.no == newNode.no) {
                flag = true;//节点存在
                break;
            }
            temp = temp.next;//向后移动
        }

        if(flag){
            System.out.printf("这个节点已在存在 %d \n",newNode.no);
        }else {
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    //显示链表数据
    public void showList(){
        if(head.next == null){
            System.out.println("此链表为空");
            return;
        }
        HeroNode temp = head.next;
        do{
            System.out.println(temp);
            temp = temp.next;
            if(temp == null){
                break;
            }
        }while (true);
    }

    /**
     * 长度
     * @return
     */
    public int length(){
        int i = 0;
        HeroNode temp = head.next;
        while (temp != null){
            ++i;
            temp = temp.next;
        }
        return i;
    }

    /**
     * 把链表反转
     * @param head 头节点
     */
    public static void reverse(HeroNode head){
        if(head.next == null || head.next.next == null){
            System.out.println("链表为空或者只有一个有效节点，不能反转");
            return;
        }
        HeroNode curr = head.next;
        HeroNode next = null;
        HeroNode reverseNode = new HeroNode(0,"","");
        while (curr != null){
            next = curr.next;//保存当前节点的下一个节点 第4部用
            curr.next = reverseNode.next;//新链表最前端 （也就是头节点的下一个） 指向 将当前节点的下一个节点
            reverseNode.next = curr;//
            curr = next;//移动节点。
        }
        //实现链表反转，更换头节点的下个一个节点
        head.next = reverseNode.next;
        //思路，使用一个新的head。遍历节点，每次插入head节点后面。最后把新的head节点next指向当前（需要反转）节点。
        //注意：插入新节点顺序。1.当前节点next临时保存。2.新head的下一个指向当前节点下一个。3.当前节点指向新节点的下一个。
        //4.当前节点下一个指向临时遍历。（现在的当前节点是新head的下一个）
    }

    //反转打印链表，不破坏结构
    public static void reversePrint(HeroNode head){
        //非空判断 略
        HeroNode cur = head.next;
        //利用栈特性，打印
        Stack<HeroNode> stack = new Stack<>();
        //保存
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //从栈中弹出
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }

    }


    public HeroNode getHead() {
        return head;
    }
}
class HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no,String name,String nickName){
        this.no=no;
        this.name=name;
        this.nickName = nickName;
    }
    public HeroNode(){}

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
